Interactive animated computer generated graphics (e.g., computer video games) which feature realistic three-dimensional animated human characters are becoming increasingly popular. As the speed and processing power of microprocessors continues to increase, the rendering quality for the interactive animated computer generated graphics has increased significantly. Measured in terms of the number of graphics primitives processed (e.g., polygons per second), the complexity of the graphics shading and textures used, the overall quality of animated three-dimensional (3D) human characters does not approach live-action video standards. However, the accuracy by which interactive computer generated animated graphics represent 3D animated human characters can be improved which significantly enhances the emotional impact and believability of animated applications such as video games for a user.
During a video game, a user is presented with a wide variety of situations (e.g., a character being chased, striving for a goal, etc.). To be realistic, the user of a video game with animated 3D human characters must be able to change the movement of the animated 3D human character substantially at any time in response to a variety of situations. The animated characters should also move in ways that accurately mimic the way human beings move in similar situations. The user response is dependent on a large number of factors (e.g., the skill of the user, the level of difficulty of the video game presented or chosen by the user, the particular segment of the video game the user is playing, etc.). Presented with the same situation in a video game N-number of times, the user may make N-number of choices, and expect the animated human character to respond realistically to each of these N-number of choices. Responding to any of a large number of user choices at any instant of time creates a degree of uncertainty for moving an animated 3D character for video games that is not present when animated 3D characters are produced for non-interactive or fixed video applications such as television or motion pictures. For non-interactive television and motion pictures the motion of animated 3D characters between the image frames is predefined to high degree of certainty, which is not true for video games under the control of a user.
Producing realistic animated 3D character motion for video games and other interactive applications presents a number of challenging problems. Existing 3D animation tools developed primarily for television, video and motion picture animation provide support for creating a single linear stream of motion data where the entire motion of an animated 3D character is planned in advance by a human animator and computed off-line (i.e., independently of when the animation is played or presented and not in real-time relative to the presentation of the animation to the user). Hand animation using existing 3D animation tools is very labor intensive, expensive and slow.
Video games with animated 3D characters under the control of a user cannot use such tools because of the real-time inputs by a user and the real-time computations required to move the animated character in response to such inputs. The entire motion of an animated 3D character also cannot be planned or created in advance because responses a human user might input during the course of the video game are too numerous to predict. In addition, developers who create interactive video games typically have much smaller budgets than television, video, or motion picture productions do and must provide a wide variety of entertainment (e.g., many different scenes and scenarios) to justify the purchase price of the video game. This greatly increases the difficulty of crafting animation for interactive applications since more 3D human character animation manipulation has to be done for a video game, but at much lower cost than is typical for television, video, or a motion picture production.
As is known in the art, the generation of a small set of high-quality motions, called basis motions, makes the creation of animated 3D human characters easier. For example, basis motions might be walk cycles, arm waves, kicks, etc. There are several companies including Acclaim Studios, in Glen Cove, N.Y., Ascension Technology in Burlington, Vt., Biovision, in San Francisco, Calif., Homer and Associates, in Hollywood, Calif., Polhemus, in Colchester, Vt. and others which produce basis motion data using a human model that includes human body segments (e.g., trunk, arms, legs, etc.) and the human joints which couple the segments (e.g., hips, elbows, wrists, shoulders, etc.).
A typical technique used to produce such basis motions for a model of a human being is to attach multiple electrical motion sensors (e.g., inertia sensors) at the joints and body segments of a person. The person goes through a set of motions (e.g., walks, runs, waves, kicks, etc.) and the sensors record the motions as a series of basis motion data points for each motion. This conventional manner of capturing basis motion data and converting it into a usable format is very expensive.
The generated basis motions include multiple degrees of freedom for each joint in the human body model. Motion degrees of freedom describe an allowable angular motion for a joint with respect to the segment to which the joint is attached. The number of motion degrees of freedom is the number of orthogonal axes about which the joint axis is free to rotate about the segment. Basis motions also include up to three position degrees of freedom to establish the position of the entire figure.
Motion capture data for a graphical object model is produced with three motion degrees of freedom for each joint, and sometimes three position degrees of freedom. For example, Ascension Technology and Polhemus produce six degrees of freedom, measuring three positional coordinates of a joint position (X,Y,Z) and three motion or orientation angles of the joint (e.g., pitch, roll, and yaw.) However, only a small number of human joints actually have three motion degrees of freedom (e.g., the shoulder joint). Most human joints only have one or two motion degrees of freedom. The motion degrees of freedom in the basis motions for a majority of the joints of a basis motion used for a human body model allow the animated character to move joints in ways that are impossible for a real person. These extra degrees of motion freedom make the 3D human character less realistic and make it more computationally expensive to use such basis motions since anatomically extraneous degrees of freedom are used in calculations to determine the motion of the animated 3D human character, even though real human joints cannot move in a similar manner.
The individual basis motions (e.g., walking, waving, etc.) generated for a model of the human body are often combined to form a composite motion (e.g., waving while walking). The composite motion typically requires that a transition motion be generated between the individual basis motions. The transition motions should provide smooth transitions between the individual basis motions. For example, a walking basis motion and a running basis motion are combined to animate a walking 3D human character that begins to run. If a high quality transition motion is not properly generated between the walk and the run basis motions, the animated 3D human character would exhibit a very jerky and unrealistic transition between the walking and the start of the running. The animated 3D human character may appear to instantaneously "leap" from the walk into running, which would be an inaccurate representation of the motion of a real person. Thus, it is important to properly generate motion transitions between individual basis motions.
The generation of motion with spacetime constraints is discussed by Andrew Witken and Michael Kass in "Spacetime Constraints," Proceedings of SIGGRAPH'88, August 1988, pages 159-168, and the generation of motion with inverse kinematics is discussed by Jianmin Zhao and Norman I. Balder in "Inverse Kinematics Positioning Using Nonlinear Programming for Highly Articulated Figures" ACM Transactions on Graphics, October 1994, Volume 13, Number 4, pages 313-336.
In the context of 3D character animation, the "space" in spacetime refers to the generalized coordinates that define an animated figure's position (e.g., the global position in space defined by position coordinates (X,Y,Z)). The values of this position vary across "time" and are represented by a function of time. Kinematics refers to modeling an animated figure with a set of rigid segments connected by joints. Joint angles define the geometric relationship between two adjacent rigid segments. Given a set of joint angles, the configuration of the segments of an animated figure can be computed. Inverse kinematics refers to finding a set of joint angles given a desired position and orientation of some segment of the figure. The spacetime and inverse kinematic techniques described in the papers listed above are limited to animation models with a small number of joints (e.g., 5), each with a small number of motion degrees of freedom (e.g., 4-6) and typically require a large amount of computation time to correctly generate transition motions. As a result, these techniques are typically not suited for real-time animation of complex graphical characters (e.g., a 3D human character).
The generation of motion transitions has also been done with motion transition processes including dynamic time warping, Fourier interpolation, and multi-resolution signal processing. However, these techniques result in transition motions which do not have realistic dynamic motion qualities and which do not satisfy kinematic constraints.
In accordance with the present invention, the problems associated with interactive animated 3D human characters are overcome. The present invention includes a method and system for generating new motions by generating motion transitions between basis motions and by cyclifying existing basis motions while maintaining constraints.
The method includes selecting a computer object model (i.e., any object real or imaginary that can be modeled with acts and symbolic represenations of operations that are preformed by a computer) for a graphical object to be animated, where the computer object model includes a body or trunk with multiple segments coupled at joints attached to the body that are moveable with multiple allowable degrees of freedom, and one or more of the joints are moveable with fewer than all of the allowable degrees of freedom. The computer object model is applied to a set of basis motions to create a processed set of basis motions. Two or more individual basis motions from the set of processed basis motions are selected to create an initial composite motion. A set of motion transitions is generated between the selected basis motions, and a final composite motion is assembled from the initial composite motion and the generated set of motion transitions. The final composite motion is used to animate a 3D graphical object (e.g., a 3D animated human character).
In the present invention, the computer object model is an optimized model of a human body which includes removing anatomically impossible motion degrees of freedom from the joint data in the basis motions to decrease the degrees of freedom in the basis motions. The optimized basis motions are decreased in size thereby improving the computational speed when the optimized basis motions are used in the generated composite motions. The motion transition generation process includes a combination of a fast spacetime constraints optimization process and an inverse kinematic optimization process to generate transitions between the optimized basis motions. This process generates motion transitions which minimize the torque needed to change an animated object from one optimized basis motion to another. The method allows use of spacetime constraints and inverse kinematics on an animated object with a large number of joints and many degrees of freedom.
The method of the present invention also includes generating motion cyclification for an optimized cyclic basis motion. A cyclic basis motion is a motion unit from which a repetitive or cyclified motion is formed (e.g., walking is a repetitive sequence of a cyclic basis motion that includes single successive right and left foot steps.). A cyclic basis motion typically does not begin and end with the character segments in the same positions or orientations. Concatenation of such basis motions creates perceptible discontinuities at the beginning and end of each cycle. Motion cyclification modifies cyclic basis motions so that character segments at the beginning and end have matched positions and orientations. This reduces cyclic motion discontinuities at the beginning and end of each motion cycle.
The present invention includes a computer software program which has an interpreter of a motion expression language called "motion algebra" to allow the user to manipulate un-optimized basis motion data, disassemble it into components, optimize it, and reassemble it into new, more complex, optimized composition motions. In addition to such editing facilities provided by the motion expression editor, the present invention includes computer-executed methods for generating motion transitions and motion cyclifications described above.
The present invention also includes a user interface with an animation preview display window and graphical controls for displaying and controlling animation images, an animation editor display window and graphical controls for displaying and controlling a motion expression editor, and an animation control display window and graphical display for displaying and controlling animation image parameters relating to the animation images. However, the user interface for the present invention can also include more or fewer windows and graphical controls.
The system for the present invention includes a database for storing optimized basis motions, a motion expression editor for manipulating the optimized basis motions, a motion transition module for generating motion transitions between two or more basis motions, a motion cyclification error reduction module for reducing motion cyclification errors for selected ones of the basis motions, and a user interface as was described above. However, the system for the present invention can also include more or fewer system components.
The present invention has been used to create optimized basis motions, optimized motion cyclifications, and optimized motion transitions for a 3D animated human character using a human body model having joints with a total of 44 motion degrees of freedom. The method and system significantly reduces the time and human labor required to animate a 3D graphical object and significantly reduces the overall cost for developing interactive computer applications, such as video games, which use animated 3D graphical characters.
The foregoing and other features and advantages of the present invention will be more readily apparent from the following detailed description, which proceeds with reference to the accompanying drawings.